public class EquationsPossible {

    public boolean equationsPossible(String[] equations) {
        Union union = new Union(26);
        for (String equation : equations) {
            if (equation.charAt(1) == '=') {
                union.merge(equation.charAt(0) - 'a', equation.charAt(3) - 'a');
            }
        }
        for (String equation : equations) {
            if (equation.charAt(1) == '!' && union.isConnect(equation.charAt(0) - 'a', equation.charAt(3) - 'a')) {
                return false;
            }
        }
        return true;
    }

    class Union {
        private int[] parent;
        public Union(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            while (parent[i] != i) {
                parent[i] = parent[parent[i]];
                i = parent[i];
            }
            return i;
        }

        public boolean isConnect(int i, int j) {
           return find(i) == find(j);
        }

        public void merge(int i, int j) {
            parent[find(i)] = find(j);
        }
    }
}
